/*
struct RandomListNode {
    int label;
    struct RandomListNode *next, *random;
    RandomListNode(int x) :
            label(x), next(NULL), random(NULL) {
    }
};
*/
/*
1、复制元素结点；每遍历一个结点，就复制一个，连接在一起；
2、处理random指针，p指向第一个结点，p->next->random=p->random->next;p=p->next->next;
3、拆分链表
*/
class Solution {
public:
    RandomListNode* Clone(RandomListNode* head) {
        auto p=head;
        while(p)
        {
            auto newp=new RandomListNode(p->label);
            newp->next=p->next;
            p->next=newp;
            p=p->next->next;
        }
        p=head;
        while(p)
        {
            if(p->random)
            {
                p->next->random=p->random->next;
                p=p->next->next;
            }
            else{
            p=p->next->next;
            }
        }
        auto dummy=new RandomListNode(-1);
        
        auto cur=dummy;
        for(p=head;p;p=p->next)
        {
            cur->next=p->next;
            cur=p->next;
            p->next=p->next->next;
        }
        return dummy->next;
    }
};